package com.banmao.algorithm.No501To700.No654;

import lombok.Data;

public class Solution1 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {

        TreeNode root = recursive(nums);
        return root;

    }

    private TreeNode recursive(int[] nums) {

        if(nums.length <= 0) {
            return null;
        }

        int max = Integer.MIN_VALUE;
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            if(max < nums[i]) {
                max = nums[i];
                index = i;
            }
        }

        TreeNode root = new TreeNode(max);
        int[] leftNums = new int[index];
        for (int i = 0; i < index; i++) {
            leftNums[i] = nums[i];
        }
        root.left = recursive(leftNums);


        int[] rightNums = new int[nums.length - (index + 1)];
        for (int i = 0, j = index + 1; i < nums.length - (index + 1); i++) {
            rightNums[i] = nums[j++];
        }
        root.right = recursive(rightNums);

        return root;

    }

}

@Data
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
